package com.cty._05_Ability._53_02_MissingNumber;

/**
 * @Auther: cty
 * @Date: 2020/7/21 16:29
 * @Description: 面试题53（二）：0到n-1中缺失的数字
 * 题目：一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字
 * 都在范围0到n-1之内。在范围0到n-1的n个数字中有且只有一个数字不在该数组
 * 中，请找出这个数字。
 * @version: 1.0
 */
public class MissingNumber {

    public static int missingNumber(int[] sortedArray){
        if(sortedArray==null || sortedArray.length==0)
            return -1;

        int lowerBound = 0;
        int upperBound = sortedArray.length - 1;
        while(true){
            if(lowerBound > upperBound)
                return -1;

            int medianIndex = lowerBound + ((upperBound-lowerBound)>>1);
            if(sortedArray[medianIndex] != medianIndex){
                if(medianIndex==0 || (medianIndex>0 && sortedArray[medianIndex-1]==medianIndex-1))
                    return medianIndex;
                else
                    upperBound = medianIndex - 1;
            }else
                lowerBound = medianIndex + 1;
        }
    }  // end missingNumber()

}  // end class
